package removeNthFromEnd19;


public class RemoveNthFromEnd {


    public ListNode removeNthFromEnd(ListNode head, int n) {
        //采用快慢指针的方式，核心就是找出要删除的节点的前一个节点
        ListNode fast = head;//快指针
        ListNode slow = head;//慢指针
        //快指针先走n步，之后在让快慢一起往后走，当快指针的next是null的时候，慢指针就是要删除节点的前一个
        for(int i = 0; i < n; i++){
            fast = fast.next;
        }
        //说明是头结点
        if(fast == null){
            return head.next;
        }
        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }

        //这个时候slow所指向的就是要删除节点的前一个节点
        slow.next = slow.next.next;

        return head;

    }

}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}